package com.javaDemo.ti;

import java.util.*;

/**
 * 动态规划变体类算法题详解
 * 
 * @author csy
 * @description 面试中常见的动态规划变体和经典题目的详细解析
 */
public class DynamicProgrammingVariants {

    /**
     * 【区间DP】最长回文子序列
     * 
     * 问题描述：
     * 给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。
     * 可以假设s的最大长度为1000。
     * 
     * 解题思路详解：
     * 1. 为什么用区间DP？
     * - 回文串具有对称性，可以从小区间扩展到大区间
     * - 子问题的解可以推导出更大问题的解
     * 
     * 2. 状态定义：
     * dp[i][j]: 表示s[i...j]中最长回文子序列的长度
     * 
     * 3. 状态转移方程推导：
     * a) 当s[i] == s[j]时：
     * dp[i][j] = dp[i+1][j-1] + 2
     * 原理：两端字符相同，可以将它们加入回文序列
     * 
     * b) 当s[i] != s[j]时：
     * dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
     * 原理：两端字符不同，只能选择其中一个字符
     * 
     * 4. 遍历顺序：
     * - 由于dp[i][j]依赖于dp[i+1][j-1]
     * - 需要从下到上，从左到右遍历
     * 
     * 5. 举例详解：
     * 输入："bbbab"
     * 过程：
     * 1) 初始化：所有单个字符长度为1
     * 2) 长度为2的子串：
     * "bb" -> 2, "ba" -> 1, "ab" -> 1
     * 3) 长度为3的子串：
     * "bbb" -> 3, "bba" -> 2, "bab" -> 3
     * ...
     * 
     * 时间复杂度：O(n²)
     * 空间复杂度：O(n²)
     */
    public static int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0)
            return 0;

        int n = s.length();
        int[][] dp = new int[n][n];

        // 初始化：单个字符的回文长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 从下到上，从左到右遍历
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }

    /**
     * 【状态压缩DP】分割等和子集
     * 
     * 问题描述：
     * 给你一个 只包含正整数 的 非空 数组 nums。判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 
     * 解题思路详解：
     * 1. 为什么用状态压缩DP？
     * - 问题可以转化为0-1背包问题
     * - 使用一维数组优化空间复杂度
     * 
     * 2. 问题转化：
     * - 目标和为数组和的一半
     * - 寻找一个子集，其和恰好为目标值
     * 
     * 3. 状态定义：
     * dp[j]: 表示是否可以用数组中的数字组成和为j
     * 
     * 4. 状态转移方程推导：
     * dp[j] = dp[j] || dp[j - nums[i]]
     * 原理：
     * - 当前数字nums[i]不使用：保持dp[j]原值
     * - 使用nums[i]：检查dp[j - nums[i]]是否为true
     * 
     * 5. 优化策略：
     * a) 提前判断：
     * - 数组和为奇数时直接返回false
     * - 任何数字大于目标和时返回false
     * 
     * b) 从后向前遍历：
     * - 避免重复使用同一个数字
     * 
     * 6. 举例详解：
     * 输入：[1,5,11,5]
     * 目标和：11
     * 
     * 过程：
     * 1) dp[0] = true
     * 2) 处理1：dp[1] = true
     * 3) 处理5：dp[6] = true, dp[5] = true
     * 4) 处理11：dp[11] = false, dp[12] = true
     * 5) 处理5：dp[11] = true
     * 
     * 时间复杂度：O(n*target)，其中target是数组和的一半
     * 空间复杂度：O(target)
     */
    public static boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 2)
            return false;

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 和为奇数，无法平分
        if (sum % 2 != 0)
            return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            // 从后向前遍历，避免重复使用同一个数字
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }

    /**
     * 【树形DP】打家劫舍III
     * 
     * 问题描述：
     * 在上次打劫完一条街道之后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。
     * 除了root之外，每栋房子有且只有一个"父"房子与之相连。一番侦察之后，聪明的小偷意识到"这个地方的所有房屋的排列类似于一棵二叉树"。
     * 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
     * 给定二叉树的root。返回在不触动警报的情况下，小偷能够盗取的最高金额。
     * 
     * 解题思路详解：
     * 1. 为什么用树形DP？
     * - 问题具有树形结构特征
     * - 每个节点的状态依赖于其子节点
     * 
     * 2. 状态定义：
     * 对于每个节点，维护两个状态：
     * - 选中该节点的最大值
     * - 不选中该节点的最大值
     * 
     * 3. 状态转移方程推导：
     * a) 选中当前节点：
     * - 当前节点值 + 左子节点不选中的最大值 + 右子节点不选中的最大值
     * 
     * b) 不选中当前节点：
     * - max(左子节点选中的最大值, 左子节点不选中的最大值) +
     * max(右子节点选中的最大值, 右子节点不选中的最大值)
     * 
     * 4. 实现策略：
     * - 使用后序遍历
     * - 返回一个长度为2的数组表示两种状态
     * 
     * 5. 举例详解：
     * 输入：[3,2,3,null,3,null,1]
     * 3
     * / \
     * 2 3
     * \ \
     * 3 1
     * 
     * 过程：
     * 1) 叶子节点3：[3,0]
     * 2) 叶子节点1：[1,0]
     * 3) 节点2：[5,3]
     * 4) 节点3：[4,1]
     * 5) 根节点3：[7,9]
     * 
     * 时间复杂度：O(n)，其中n是节点数
     * 空间复杂度：O(h)，其中h是树的高度
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static int rob(TreeNode root) {
        int[] result = robHelper(root);
        return Math.max(result[0], result[1]);
    }

    private static int[] robHelper(TreeNode node) {
        if (node == null)
            return new int[] { 0, 0 };

        // 后序遍历
        int[] left = robHelper(node.left);
        int[] right = robHelper(node.right);

        int[] result = new int[2];
        // 选中当前节点
        result[0] = node.val + left[1] + right[1];
        // 不选中当前节点
        result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return result;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试最长回文子序列
        System.out.println("=== 最长回文子序列测试 ===");
        String s1 = "bbbab";
        System.out.println("输入字符串：" + s1);
        System.out.println("最长回文子序列长度：" + longestPalindromeSubseq(s1) + "\n");

        // 测试分割等和子集
        System.out.println("=== 分割等和子集测试 ===");
        int[] nums = { 1, 5, 11, 5 };
        System.out.println("输入数组：" + Arrays.toString(nums));
        System.out.println("是否可以分割：" + canPartition(nums) + "\n");

        // 测试打家劫舍III
        System.out.println("=== 打家劫舍III测试 ===");
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        System.out.println("最大抢劫金额：" + rob(root));
    }
}